package linkList;

import utils.linkListUtil;
import utils.linkListUtil.ListNode;

public class addTwoNumbers {
    // 就是迭代，omax（m，n） 注意长度不同时，最后一位可能要进位
    public static ListNode addTwoNumbers1(ListNode l1, ListNode l2) {
        // l1和l2长度不一样
        ListNode head = new ListNode(0, null);
        ListNode curr = head, pre = head;
        int count = 0;
        boolean flag = false;
        while (l1 != null && l2 != null) {
            // 1234 12
            // count最大为1
            curr.val = l1.val + l2.val + count;
            // 重置
            count = 0;
            if (curr.val > 9) {
                count++;
                curr.val %= 10;
            }
            pre = curr;
            curr = new ListNode(0, null);
            if (l1.next != null && l2.next != null) {
                pre.next = curr;
                l1 = l1.next;
                l2 = l2.next;
            } else {
                l1 = l1.next;
                l2 = l2.next;
                break;
            }

        }
        
        if (l1 == null && l2 != null) {
            pre.next=curr;
            while (l2 != null) {
                // 保留了之前的count
                curr.val = l2.val + count;
                // 重置
                count = 0;
                if (curr.val > 9) {
                    count++;
                    curr.val %= 10;
                }
                pre = curr;
                curr = new ListNode(0, null);
                if (l2.next != null) {
                    pre.next = curr;
                    l2 = l2.next;
                } else {
                    break;
                }
            }

        } else if (l1 != null && l2 == null) {
            pre.next=curr;
            while (l1 != null) {
                // 保留了之前的count
                curr.val = l1.val + count;
                // 重置
                count = 0;
                if (curr.val > 9) {
                    count++;
                    curr.val %= 10;
                }
                pre = curr;
                curr = new ListNode(0, null);
                if (l1.next != null) {
                    pre.next = curr;
                    l1 = l1.next;
                } else {
                    break;
                }
            }

        }
        // count!=0
        if (count!=0) {
            curr.val=1;
            pre.next=curr;
        }
        return head;
    }
    public static ListNode addTwoNumbers2(ListNode l1, ListNode l2) {
        //长度不一样长
        //注意两个进位，一个是短的结束时，另一个是长的结束时
        ListNode node1 = l1, node2 = l2;
        int carry = 0;
        while (node1 != null && node2 != null) {
            //统一加到l1中
            int sum = node1.val + node2.val + carry;
            if (sum > 9) {
                sum %= 10;
                carry = 1;
            }else{
                carry=0;
            }
            node1.val = sum;
            node2.val = sum;
            if (node1.next == null && node2.next == null) {
                //长度一样
                if (carry == 1) {
                    ListNode newNode = new ListNode(1);
                    node1.next = newNode;
                }
                return l1;
            }
            node1 = node1.next;
            node2 = node2.next;

        }
        //长度不一致
        if (node1 != null) {
            int sum = node1.val + carry;
            if (sum > 9) {
                carry = 1;
                sum %= 10;
            }else{
                carry=0;
            }
            node1.val = sum;
            if (node1.next == null) {
                if (carry == 1) {
                    ListNode newNode = new ListNode(1);
                    node1.next = newNode;
                }
                return l1;
            }
            node1 = node1.next;
        } else {
            int sum = node2.val + carry;
            if (sum > 9) {
                carry = 1;
                sum %= 10;
            }else{
                carry=0;
            }
            node2.val = sum;
            if (node2.next == null) {
                if (carry == 1) {
                    ListNode newNode = new ListNode(1);
                    node2.next = newNode;
                }

                return l2;
            }
            node2 = node2.next;
        }
        return null;
    }

    public static void main(String[] args) {
        int[] a=new int[]{9,9,9,9,9,9,9};
        int[] b=new int[]{9,9,9,9};
        ListNode headA = linkListUtil.createLinkedList(a);
        ListNode headB = linkListUtil.createLinkedList(b);
        ListNode rs = addTwoNumbers2(headA, headB);
        while (rs!=null) {
            System.out.println(rs.val);
            rs=rs.next;
        }
    }
}
